#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>
#include "mymem.h"
#include <time.h>

#define TRUE 1
#define FALSE 0

typedef int bool;

#include <sys/types.h>
#include <unistd.h>

/*!
 * \file list.h
 * \brief Definition for the doubly linked list class.
 * \author Vijay Ramesh
 *
 * This is a simple doubly linked list class.
 */


struct list_t;
struct lnode_t;

typedef struct lnode_t lnode_t;
typedef struct list_t list_t;

/*!
 * \brief A doubly linked list node struct.
 *
 * This is a simple list node class with 3 pointers, next, prev, value.
 * next points to the next node in the list. prev points to the
 * previous node in the list. value is a void pointer to the address of
 * the object being held in the listnode.
 */
struct lnode_t
{
   lnode_t *next; /*!< next points to the next node in the list. NULL if at the
                       end of the list.*/
   lnode_t *prev; /*!< prev points to the previous node in the list. NULL if at
                    the beginning of the list.*/
   void *value;   /*!< value points to the structure held by the list node. NULL
                       if empty.*/
};

/*!
 * \brief A doubly linked list struct.
 *
 * This is a simple list struct with 3 pointers, front, back, current and two
 * helper variables, empty, and size. front points to the front of the list.
 * back points to the back of the list. current points to the current location
 * on the list. empty is a bool, that is set to false when the list is not empty
 * and true when the list is empty. size is the lize of the list.
 */
struct list_t
{
   lnode_t *front;   /*!< front points to the lnode_t at the front of the
                          list. NULL if list is empty.*/
   lnode_t *current; /*!< current points to the lnode_t currently positioned at.
                          NULL if list is empty.*/
   lnode_t *back;    /*!< back points to the lnode_t at the back of the list.
                          NULL if list is empty.*/
   bool empty;       /*!< empty is a boolean that is set to TRUE if the list
                          contains no nodes, and is FALSE if the list contains
                          nodes.*/
   int size;         /*!< size is always set to the size of the list. 0 when
                          list is empty.*/
};

/*!
 * \brief The initializer for the list object.
 *
 * This sets all the pointers in the list object to NULL, size to 0, and empty
 * to true.
 *
 * \param list is the list_t pointer.
 */
void l_init ( list_t *list );

/*!
 * \brief An insert before function
 *
 * This inserts a value right before the current pointer in the list.
 *
 * \param list is the list_t pointer.
 * \param value is a pointer to the value to be inserted.
 * \return Returns an int, 0 on success and 1 on failure.
 */
int l_ins_before ( list_t *list, void *value );

/*!
 * \brief An insert after function
 *
 * This inserts a value right after the current pointer in the list.
 *
 * \param list is the list_t pointer.
 * \param value is a pointer to the value to be inserted.
 * \return Returns an int, 0 on success and 1 on failure.
 */
int l_ins_after ( list_t *list, void *value );

/*!
 * \brief A push front function
 *
 * This pushes a value onto the front of the list.
 *
 * \param list is the list_t pointer.
 * \param value is a pointer to the value to be pushed.
 * \return Returns an int, 0 on success and 1 on failure.
 */
int l_push_front ( list_t *list, void *value );

/*!
 * \brief A push back function
 *
 * This pushes a value onto the back of the list.
 *
 * \param list is the list_t pointer.
 * \param value is a pointer to the value to be pushed.
 * \return Returns an int, 0 on success and 1 on failure.
 */
int l_push_back ( list_t *list, void *value );

/*!
 * \brief A pop function
 *
 * This pops the node pointed to by current and returns a pointer to the value
 * held there.
 *
 * \param list is the list_t pointer.
 * \return Returns A pointer to the value at the node just popped.
 */
void * l_pop ( list_t *list );

/*!
 * \brief A pop front function
 *
 * This moves to the front and then calls pop ();
 *
 * \param list is the list_t pointer.
 * \return Returns A pointer to the value at the node just popped, in this case
 *         the front of the list.
 */
void * l_pop_front ( list_t *list );

/*!
 * \brief A pop back function
 *
 * This moves to the back and then calls pop ();
 *
 * \param list is the list_t pointer.
 * \return Returns A pointer to the value at the node just popped, in this case
 *         the queue of the list.
 */
void * l_pop_back ( list_t *list );

/*!
 * \brief A move next function
 *
 * This sets current to the next pointer.
 *
 * \param list is the list_t pointer.
 * \return Returns an int, 0 on success and 1 on failure.
 */
int l_move_n ( list_t *list );

/*!
 * \brief A move previous function
 *
 * This sets current to the previous pointer.
 *
 * \param list is the list_t pointer.
 * \return Returns an int, 0 on success and 1 on failure.
 */
int l_move_p ( list_t *list );

/*!
 * \brief A goto front function
 *
 * This sets current to the front. Effectively going to the front of the list.
 *
 * \param list is the list_t pointer.
 */
void l_front ( list_t *list );

/*!
 * \brief A goto back function
 *
 * This sets current to the back. Effectively going to the back of the list.
 *
 * \param list is the list_t pointer.
 */
void l_back ( list_t *list );

/*!
 * \brief A reverse function
 *
 * This reverses the the current list. Current will point to the front of the
 * reversed list [ aka the back of the list before being reversed ].
 *
 * \param list is the list_t pointer.
 */
void l_reverse ( list_t *list );

/*!
 * \brief A destroy function
 *
 * This deletes all the space held by list. The values held by each listnode are
 * not deleted.
 *
 * \param list is the list_t pointer.
 */
void l_destroy ( list_t *list );

/*!
 * \brief A set empty function
 *
 * This sets the empty variable in the list_t by determinig is the list is
 * empty. This is mainly an internal function and never needs to be called upon,
 * although you can call it if you feel like it.
 *
 * \param list is the list_t pointer.
 */
void l_set_empty ( list_t *list );

/*!
 * \file list.c
 * \brief Implementation for the doubly linked list class.
 * \author Vijay Ramesh
 *
 * This is a simple doubly linked list class.
 */

void l_init ( list_t *list )
{
   list->front = NULL;
   list->current = NULL;
   list->back = NULL;
   list->empty = TRUE;
   list->size = 0;
   return;
}

int l_ins_before ( list_t *list, void *value )
{
   lnode_t *temp_node;
   temp_node = ( lnode_t *) malloc ( sizeof ( lnode_t ));
   if ( temp_node == NULL )
   {
      /* Out of memory */ 
      return 1;
   }
   else
   {
      if ( list->empty )
      {
         /* list is empty */
         temp_node->next = NULL;
         temp_node->prev = NULL;
         temp_node->value = value;
         list->back = temp_node;
         list->front = temp_node;
         list->current = temp_node;
         list->size++;
         l_set_empty ( list );
         /* Sucess */
      }
      else
      {
         /* list is not empty */
         if ( list->current->prev == NULL )
         {
            /* inserting at front */
            list->current->prev = temp_node;
            temp_node->prev = NULL;
            temp_node->next = list->current;
            temp_node->value = value;
            list->front = temp_node;
            list->current = temp_node;
         }
         else
         {
            /* not inserting at front */
            temp_node->prev = list->current->prev;
            temp_node->next = list->current;
            list->current->prev->next = temp_node;
            list->current->prev = temp_node;
            temp_node->value = value;
            list->current = temp_node;
         }
         list->size++;
         l_set_empty ( list );
      }
      return 0;
   }
}

int l_ins_after ( list_t *list, void *value )
{
   lnode_t *temp_node;
   temp_node = ( lnode_t *) malloc ( sizeof ( lnode_t ));
   if ( temp_node == NULL )
   {
      /* Out of memory */ 
      return 1;
   }
   else
   {
      if ( list->empty )
      {
         /* list is empty */
         temp_node->next = NULL;
         temp_node->prev = NULL;
         temp_node->value = value;
         list->back = temp_node;
         list->front = temp_node;
         list->current = temp_node;
         list->size++;
         l_set_empty ( list );
         /* Sucess */
      }
      else
      {
         /* list is not empty */
         if ( list->current->next == NULL )
         {
            /* inserting at back */
            list->current->next = temp_node;
            temp_node->prev = list->current;
            temp_node->next = NULL;
            temp_node->value = value;
            list->back = temp_node;
            list->current = temp_node;
         }
         else
         {
            /* not inserting at back */
            temp_node->next = list->current->next;
            temp_node->prev = list->current;
            list->current->next->prev = temp_node;
            list->current->next = temp_node;
            temp_node->value = value;
            list->current = temp_node;
         }
         list->size++;
         l_set_empty ( list );
      }
      return 0;
   }
}

int l_push_front ( list_t *list, void *value )
{
   list->current = list->front;
   return l_ins_before ( list, value );
}

int l_push_back ( list_t *list, void *value )
{
   list->current = list->back;
   return l_ins_after ( list, value );
}

void * l_pop ( list_t *list )
{
   if ( list->empty )
   {
      /* list is empty */
      return NULL;
   }
   else
   {
      lnode_t *temp_node;
      void *temp_ptr;
      temp_node = list->current;
      temp_ptr = list->current->value;
      if ( list->current->prev == NULL )
      {
         /* front of list */
         if ( list->current->next == NULL )
         {
            /* only element on the list */
            list->current = NULL;
            list->front = NULL;
            list->back = NULL;
         }
         else
         {
            /* not back of list */
            list->current = list->current->next;
            list->current->prev = NULL;
            list->front = list->current;
         }
      }
      else if ( list->current->next == NULL )
      {
         /* back of the list */
         if ( list->current->prev == NULL )
         {
            /* only element on the list */
            list->current = NULL;
            list->front = NULL;
            list->back = NULL;
         }
         else
         {
            /* not front of list */
            list->current = list->current->prev;
            list->current->next = NULL;
            list->back = list->current;
         }
      }
      else
      {
         /* middle of list */
         list->current->prev->next = list->current->next;
         list->current->next->prev = list->current->prev;
         list->current = list->current->next;
      }
      free ( temp_node );
      list->size--;
      l_set_empty ( list );
      return temp_ptr;
   }
}

void * l_pop_front ( list_t *list )
{
   list->current = list->front;
   return l_pop ( list );
}

void * l_pop_back ( list_t *list )
{
   list->current = list->back;
   return l_pop ( list );
}

int l_move_n ( list_t * list )
{
   if ( list->empty )
   {
      return 1;
   }
   else
   {
      if ( list->current->next == NULL )
      {
         return 1;
      }
      else
      {
         list->current = list->current->next;
         return 0;
      }
   }
}

int l_move_p ( list_t *list )
{
   if ( list->empty )
   {
      return 1;
   }
   else
   {
      if ( list->current->prev == NULL )
      {
         return 1;
      }
      else
      {
         list->current = list->current->prev;
         return 0;
      }
   }
}

void l_front ( list_t *list )
{
   list->current = list->front;
   return;
}

void l_back ( list_t *list )
{
   list->current = list->back;
   return;
}

void l_reverse ( list_t *list )
{
   if ( list->empty )
   {
      return;
   }
   else
   {
      /* list->current is valid */
      int valid;
      lnode_t *temp_node;
      valid = 0;
      list->current = list->front;
      while ( valid == 0 )
      {
         temp_node = list->current->next;
         list->current->next = list->current->prev;
         list->current->prev = temp_node;
         valid = l_move_p ( list );
      }
      temp_node = list->front;
      list->front = list->back;
      list->back = temp_node;
      list->current = list->front;
   }
}

void l_destroy ( list_t *list )
{
   while ( !list->empty )
   {
      l_pop_front ( list );
   }
   free ( list );
   return;
}

void l_set_empty ( list_t *list )
{
   if ( list->front != NULL )
   {
      list->empty = FALSE;
   }
   else
   {
      list->empty = TRUE;
   }
   return;
}

static int maxSize;

list_t mem_list;

typedef struct mem_node_t mem_node_t;
struct mem_node_t
{
   int free_space;
   int offset;
   int size;
};

lnode_t* last = NULL;

/*  Returns the total number of bytes in the memory pool. */
int mem_size ()
{
   return maxSize;
}

/* Returns the malloc implementation based on a name. */
mymalloc_fp to_malloc_implementation ( char *name )
{ // No need to modify this function
	if(name && !strcmp("best",name)) return malloc_bestfit;
	if(name && !strcmp("worst",name)) return malloc_worstfit;
	if(name && !strcmp("next",name)) return malloc_nextfit;
	if(name && !strcmp("first",name)) return malloc_firstfit;
	fprintf(stderr,"Unknown %s; expected {best|worst|next|first}\n",name);
	exit(1);
}

/*
 * Implement the following functions.
 * Note that when we refer to "memory" here, we mean the 
 * memory pool this module manages via initmem/malloc_/myfree. 
 */

/* initmem must be called prior to mymalloc and myfree.
   initmem may be called more than once in a given exeuction;
   when this occurs, all memory reviously malloc'ed must be freed,
   including any existing bookkeeping data.

    sz specifies the number of bytes that will be available, in total, for all mymalloc requests.
 */

void initmem ( int sizeInBytes )
{
	maxSize = sizeInBytes;
   l_init ( &mem_list );
   mem_node_t *space = malloc ( sizeof ( mem_node_t ));
   space->free_space = 1;
   space->offset = 0;
   space->size = maxSize;
   l_push_front ( &mem_list, ( void* ) space );
	//Add additional code here to reset your data structures
}


/* Allocate a block of memory with the requested size using the appropriate placement algorithm.
 *  If the requested block is not available, return -1.
 *  Otherwise, it returns a pointer to the newly allocated block.
 *  Restriction: requested >= 1 
 */
int malloc_bestfit ( int bytes )
{
   //printf ( "Allocate :: %i\n", bytes );
   //mem_debug_print_data ();
   int ret = -1;
   if ( bytes != 0 )
   {
     // printf ( "int first if statement \n" );
      l_front ( &mem_list );
      int size = mem_list.size;
      int i;
      lnode_t *temp = NULL;
      for ( i = 0; i < size; i++ )
      {
         if ((( mem_node_t* )( mem_list.current->value ))->free_space &&
              (((mem_node_t* )( mem_list.current->value ))->size >= bytes ))
         {
            //printf ( "before found fit\n" );
            //wohoo found a first fit. split it and insert new node.
            if ( temp != NULL )
            {
               if (((( mem_node_t* )( mem_list.current->value))->size <
                        (( mem_node_t* )( temp->value ))->size ))
               {
                  temp = mem_list.current;
               }
            }
            else
            {
               temp = mem_list.current;
            }
         }
         l_move_n ( &mem_list );
      }
      if ( temp != NULL )
      {
         mem_list.current = temp;
         if (((( mem_node_t* )( temp->value ))->size - bytes ) == 0 )
         {
            (( mem_node_t* )( mem_list.current->value))->free_space = 0;
         }
         else
         {
            mem_node_t *new_alloc = malloc ( sizeof ( mem_node_t ));
            new_alloc->free_space = 0;
            new_alloc->offset = (( mem_node_t* )( temp->value ))->offset;
            new_alloc->size = bytes;
            (( mem_node_t* )( mem_list.current->value ))->offset = new_alloc->offset + bytes;
            (( mem_node_t* )( mem_list.current->value ))->size =
               (( mem_node_t* )( mem_list.current->value))->size - bytes;
            l_ins_before ( &mem_list, ( void* ) new_alloc );
         }
         ret = (( mem_node_t* )( mem_list.current->value))->offset;
      }
   }
   //printf ( "Return :: %i\n", ret );
   return ret; /* Change this */
}

int malloc_worstfit ( int bytes )
{
   int ret = -1;
   if ( bytes != 0 )
   {
     // printf ( "int first if statement \n" );
      l_front ( &mem_list );
      int size = mem_list.size;
      int i;
      lnode_t *temp = NULL;
      for ( i = 0; i < size; i++ )
      {
         if ((( mem_node_t* )( mem_list.current->value ))->free_space &&
              (((mem_node_t* )( mem_list.current->value ))->size >= bytes ))
         {
            //printf ( "before found fit\n" );
            //wohoo found a first fit. split it and insert new node.
            if ( temp != NULL )
            {
               if (((( mem_node_t* )( mem_list.current->value))->size >
                        (( mem_node_t* )( temp->value ))->size ))
               {
                  temp = mem_list.current;
               }
            }
            else
            {
               temp = mem_list.current;
            }
         }
         l_move_n ( &mem_list );
      }
      if ( temp != NULL )
      {
         mem_list.current = temp;
         if (((( mem_node_t* )( temp->value ))->size - bytes ) == 0 )
         {
            (( mem_node_t* )( mem_list.current->value))->free_space = 0;
         }
         else
         {
            mem_node_t *new_alloc = malloc ( sizeof ( mem_node_t ));
            new_alloc->free_space = 0;
            new_alloc->offset = (( mem_node_t* )( temp->value ))->offset;
            new_alloc->size = bytes;
            (( mem_node_t* )( mem_list.current->value ))->offset = new_alloc->offset + bytes;
            (( mem_node_t* )( mem_list.current->value ))->size =
               (( mem_node_t* )( mem_list.current->value))->size - bytes;
            l_ins_before ( &mem_list, ( void* ) new_alloc );
         }
         ret = (( mem_node_t* )( mem_list.current->value))->offset;
      }
   }
   //printf ( "Return :: %i\n", ret );
   return ret; /* Change this */
}

int malloc_firstfit ( int bytes )
{
   //mem_debug_print_data ();
   int ret = -1;
   //printf ( "bytes allocated :%i\n", bytes );
   if ( bytes != 0 )
   {
     // printf ( "int first if statement \n" );
      l_front ( &mem_list );
      int size = mem_list.size;
      int i;
      for ( i = 0; i < size; i++ )
      {
         if ((( mem_node_t* )( mem_list.current->value ))->free_space &&
              (((mem_node_t* )( mem_list.current->value ))->size >= bytes ))
         {
            //printf ( "before found fit\n" );
            //wohoo found a first fit. split it and insert new node.
            if (((( mem_node_t* )( mem_list.current->value))->size - bytes ) == 0 )
            {
               //printf ( "Found first fit\n" );
               (( mem_node_t* )( mem_list.current->value))->free_space = 0;
            }
            else
            {
               mem_node_t *new_alloc = malloc ( sizeof ( mem_node_t ));
               new_alloc->free_space = 0;
               new_alloc->offset = (( mem_node_t* )( mem_list.current->value))->offset;
               new_alloc->size = bytes;
               (( mem_node_t* )( mem_list.current->value))->offset = new_alloc->offset + bytes;
               (( mem_node_t* )( mem_list.current->value))->size =
                  (( mem_node_t* )( mem_list.current->value))->size - bytes;
               l_ins_before ( &mem_list, ( void* ) new_alloc );
            }
            ret = (( mem_node_t* )( mem_list.current->value))->offset;
            break;
         }
         l_move_n ( &mem_list );
      }
   }
   return ret; /* Change this */
}

int malloc_nextfit ( int bytes )
{
   int ret = -1;
   //printf ( "Allocate :: %i\n", bytes );
   //mem_debug_print_data ();
   if ( bytes != 0 )
   {
      int size = mem_list.size;
      if ( size == 1 )
      {
         //printf ( "size == 1\n" );
         l_front ( &mem_list );
         if (((( mem_node_t* )( mem_list.current->value))->size - bytes ) == 0 )
         {
            //printf ( "Found first fit\n" );
            (( mem_node_t* )( mem_list.current->value))->free_space = 0;
         }
         else
         {
            mem_node_t *new_alloc = malloc ( sizeof ( mem_node_t ));
            new_alloc->free_space = 0;
            new_alloc->offset = (( mem_node_t* )( mem_list.current->value))->offset;
            new_alloc->size = bytes;
            (( mem_node_t* )( mem_list.current->value))->offset = new_alloc->offset + bytes;
            (( mem_node_t* )( mem_list.current->value))->size =
               (( mem_node_t* )( mem_list.current->value))->size - bytes;
            l_ins_before ( &mem_list, ( void* ) new_alloc );
         }
         last = mem_list.current;
         ret = (( mem_node_t* )( mem_list.current->value))->offset;
      }
      else
      {
         if ( last->next != NULL )
         {
            mem_list.current = last->next;
         }
         else
         {
            l_front ( &mem_list );
         }
         while ( mem_list.current != last )
         {
            //printf ( "while loop\n" );
            //printf ("free :: %i\n", (( mem_node_t* )( mem_list.current->value ))->free_space );
            //printf ("size :: %i\n", (( mem_node_t* )( mem_list.current->value ))->size );
            if ((( mem_node_t* )( mem_list.current->value ))->free_space &&
                 (((mem_node_t* )( mem_list.current->value ))->size >= bytes ))
            {
               //printf ( "before found fit\n" );
               //wohoo found a first fit. split it and insert new node.
               if (((( mem_node_t* )( mem_list.current->value))->size - bytes ) == 0 )
               {
                  //printf ( "Found first fit\n" );
                  (( mem_node_t* )( mem_list.current->value))->free_space = 0;
               }
               else
               {
                  mem_node_t *new_alloc = malloc ( sizeof ( mem_node_t ));
                  new_alloc->free_space = 0;
                  new_alloc->offset = (( mem_node_t* )( mem_list.current->value))->offset;
                  new_alloc->size = bytes;
                  (( mem_node_t* )( mem_list.current->value))->offset = new_alloc->offset + bytes;
                  (( mem_node_t* )( mem_list.current->value))->size =
                     (( mem_node_t* )( mem_list.current->value))->size - bytes;
                  l_ins_before ( &mem_list, ( void* ) new_alloc );
               }
               last = mem_list.current;
               ret = (( mem_node_t* )( mem_list.current->value ))->offset;
               //printf ( "ret == %i\n", ret );
               break;
            }
            if ( mem_list.current == mem_list.back )
            {
               //printf ( "back\n" );
            }
            if ( last == mem_list.back )
            {
               //printf ( "last back\n" );
            }
            if ( mem_list.current == mem_list.back &&
                 last != mem_list.back )
            {
               l_front ( &mem_list );
            }
            else
            {
               l_move_n ( &mem_list );
               //printf ( "called next\n" );
            }
         }
      }
   }
   //printf ( "Return :: %i\n", ret );
   return ret; /* Change this */
}

/* Frees a block of memory previously allocated by mymalloc.
 * Your implementation should check that block is valid.
 * If block is invalid (i.e. does not refer to an allocate block) then do nothing. 
 */
void myfree ( int offset )
{
   l_front ( &mem_list );
   int size = mem_list.size;
   int i;
	//Add additional code here.
	// Hint: next fit requires special handling here.

   for ( i = 0; i < size; i++ )
   {
      if (((( mem_node_t* )( mem_list.current->value))->offset == offset ) &&
          ((( mem_node_t* )( mem_list.current->value))->free_space == 0 ))
      {
         if (( mem_list.current->prev != NULL ) &&
             ( mem_list.current->next != NULL ))
         {
            // in the middle
            if (((( mem_node_t* )( mem_list.current->prev->value))->free_space == 1 ) &&
                ((( mem_node_t* )( mem_list.current->next->value))->free_space == 1 ))
            {
               int set = 0;
               if (( mem_list.current == last ) ||
                   ( mem_list.current->prev == last ) ||
                   ( mem_list.current->next == last ))
               {
                  set = 1;
               }
               // surrounded
               int size = 0;
               size += (( mem_node_t* )( mem_list.current->value))->size;
               l_pop ( &mem_list );
               size += (( mem_node_t* )( mem_list.current->value))->size;
               l_pop ( &mem_list );
               l_move_p ( &mem_list );
               (( mem_node_t* )( mem_list.current->value))->size += size;

               if ( set == 1 )
               {
                  last = mem_list.current;
               }
               return;
            }
            else if (((( mem_node_t* )( mem_list.current->prev->value))->free_space == 0 ) &&
                     ((( mem_node_t* )( mem_list.current->next->value))->free_space == 1 ))
            {
               int set = 0;
               if (( mem_list.current == last ) ||
                   ( mem_list.current->prev == last ) ||
                   ( mem_list.current->next == last ))
               {
                  set = 1;
               }
               int size = 0;
               size += (( mem_node_t* )( mem_list.current->value))->size;
               l_pop ( &mem_list );
               (( mem_node_t* )( mem_list.current->value))->size += size;
               if ( set == 1 )
               {
                  last = mem_list.current;
               }
               return;
            }
            else if (((( mem_node_t* )( mem_list.current->prev->value))->free_space == 1 ) &&
                     ((( mem_node_t* )( mem_list.current->next->value))->free_space == 0 ))
            {
               int size = 0;
               int set = 0;
               if (( mem_list.current == last ) ||
                   ( mem_list.current->prev == last ) ||
                   ( mem_list.current->next == last ))
               {
                  set = 1;
               }
               size += (( mem_node_t*)( mem_list.current->value))->size;
               l_pop ( &mem_list );
               l_move_p ( &mem_list );
               (( mem_node_t* )( mem_list.current->value))->size += size;
               if ( set == 1 )
               {
                  last = mem_list.current;
               }
               return;
            }
            else // just swapt free_space
            {
               (( mem_node_t* )( mem_list.current->value))->free_space = 1;
               return;
            }
         }
         else if (( mem_list.current->prev == NULL ) &&
                  ( mem_list.current->next != NULL ))
         {
            if ((( mem_node_t* )( mem_list.current->next->value))->free_space == 1 )
            {
               int size = 0;
               int set = 0;
               if (( mem_list.current == last ) ||
                   ( mem_list.current->next == last ))
               {
                  set = 1;
               }
               size += (( mem_node_t* )( mem_list.current->value))->size;
               l_pop ( &mem_list );
               (( mem_node_t* )( mem_list.current->value))->size += size;
               if ( set == 1 )
               {
                  last = mem_list.current;
               }
               return;
            }
            else
            {
               (( mem_node_t* )( mem_list.current->value))->free_space = 1;
               return;
            }
         }
         else if (( mem_list.current->prev != NULL ) &&
                  ( mem_list.current->next == NULL ))
         {
            if ((( mem_node_t* )( mem_list.current->prev->value))->free_space == 1 )
            {
               int size = 0;
               int set = 0;
               if (( mem_list.current == last ) ||
                   ( mem_list.current->prev == last ))
               {
                  set = 1;
               }
               size += (( mem_node_t* )( mem_list.current->value))->size;
               l_pop ( &mem_list );
               (( mem_node_t* )( mem_list.current->value))->size += size;
               if ( set == 1 )
               {
                  last = mem_list.current;
               }
               return;
            }
            else
            {
               (( mem_node_t* )( mem_list.current->value))->free_space = 1;
               return;
            }
         }
         else
         {
            // only value in the middle
            (( mem_node_t* )( mem_list.current->value))->free_space = 1;
            return;
         }
      }
      l_move_n ( &mem_list );
   }
}


/* Get the number of contiguous areas of free space in memory. */
int mem_count_holes ()
{
   l_front ( &mem_list );
   int holes = 0;
   int size = mem_list.size;
   int i;
   for ( i = 0; i < size; i++ )
   {
      if ((( mem_node_t* )( mem_list.current->value))->free_space == 1 )
      {
         holes++;
      }
      l_move_n ( &mem_list );
   }
   return holes; /* Change this */
}

/* Get the number of bytes allocated */
int mem_bytes_allocated ()
{
   l_front ( &mem_list );
   int bytes = 0;
   int size = mem_list.size;
   int i;
   for ( i = 0; i < size; i++ )
   {
      if ((( mem_node_t* )( mem_list.current->value))->free_space == 0 )
      {
         bytes += (( mem_node_t* )( mem_list.current->value))->size;
      }
      l_move_n ( &mem_list );
   }
   return bytes; /* Change this */
}


/* Number of non-allocated bytes */
int mem_bytes_free ()
{
   l_front ( &mem_list );
   int bytes = 0;
   int size = mem_list.size;
   int i;
   for ( i = 0; i < size; i++ )
   {
      if ((( mem_node_t* )( mem_list.current->value))->free_space == 1 )
      {
         bytes += (( mem_node_t* )( mem_list.current->value))->size;
      }
      l_move_n ( &mem_list );
   }
   return bytes; /* Change this */
}

/* Number of bytes in the largest contiguous area of unallocated memory */
int mem_bytes_largest_hole ()
{
   l_front ( &mem_list );
   int bytes = 0;
   int size = mem_list.size;
   int i;
   for ( i = 0; i < size; i++ )
   {
      if ((( mem_node_t* )( mem_list.current->value))->free_space == 1 )
      {
         if ((( mem_node_t* )( mem_list.current->value))->size > bytes )
         {
            bytes = (( mem_node_t* )( mem_list.current->value))->size;
         }
      }
      l_move_n ( &mem_list );
   }
   return bytes; /* Change this */
}


/* Number of free blocks smaller than or equal to "size" bytes. */
int mem_count_small_holes ( int size )
{
   l_front ( &mem_list );
   int blocks = 0;
   int list_size = mem_list.size;
   int i;
   for ( i = 0; i < list_size; i++ )
   {
      if ((( mem_node_t* )( mem_list.current->value))->free_space == 1 )
      {
         if ((( mem_node_t* )( mem_list.current->value))->size <= size )
         {
            blocks++;
         }
      }
      l_move_n ( &mem_list );
   }
   return blocks; /* Change this */
}

/* Returns 1 if the byte is allocated */
char mem_is_allocated ( int offset )
{
   l_front ( &mem_list );
   int ret = 0;
   int size = mem_list.size;
   int i;
   for ( i = 0; i < size; i++ )
   {
      if ((( mem_node_t* )( mem_list.current->value))->offset == offset )
      {
         if ((( mem_node_t* )( mem_list.current->value))->free_space == 0 )
         {
            ret = 1;
         }
      }
      l_move_n ( &mem_list );
   }
   return ret;
}


/* 
 * These functions are for you to modify however you see fit.  These will not
 * be used in tests, but you may find them useful for debugging.
 */

/* Use this function to print out the current contents of memory / data structures etc. */
void mem_debug_print_data ()
{
   lnode_t *curr = mem_list.current;
   l_front ( &mem_list );
   int size = mem_list.size;
   int i;
   printf ( "Turn\n\n" );
   for ( i = 0; i < size; i++ )
   {
      printf ( "bytes: %i, free: %i\n", ((mem_node_t*)( curr->value))->size, ((mem_node_t*)( curr->value))->free_space);
      l_move_n ( &mem_list );
   }
   printf ( "bytes: %i, free: %i\n", ((mem_node_t*)( curr->value))->size, ((mem_node_t*)( curr->value))->free_space);
   printf ( "\n\n" );
   mem_list.current = curr;
	return; // this function is ungraded
}

/* Use this function to track memory allocation performance.  
 * This function does not depend on your implementation, 
 * but on the functions you wrote above.
 */ 
void mem_debug_print_statistics ()
{
	// this function is ungraded
	printf("%d out of %d bytes allocated.\n",mem_bytes_allocated(),mem_size());
	printf("%d bytes are free in %d holes; maximum allocatable block is %d bytes.\n",mem_bytes_free(),mem_count_holes(),mem_bytes_largest_hole());
	printf("Average hole size is %f.\n\n",((float)mem_bytes_free())/mem_count_holes());
}
